A programmable logic array device has a plurality of logic elements connected through an interconnect architecture. Electrical circuits are mapped over these logic elements to allow the device to perform desired operations. Mapping of an electrical circuit to an FPGA is a time consuming process, and thus it is desired to increase the speed of the mapping process.
The important objectives during mapping of an electrical circuit over an FPGA are, to map the maximum number of circuit elements over a single logic element and to achieve the smallest possible tree of logic elements to realize the electrical circuit. Different technologies propose different methods for achieving these objectives. For example, R. J. Francis et al. in “Chortle-crf: Fast Technology Mapping for Lookup Table-Based FPGAs”, University of Toronto, CA 28th ACM/IEEE Design Automation Conference, 1991, pp. 227–233, proposes a mapping algorithm that reduces delay by using bin packing to determine the gate level decomposition of every node in the network.
Another method suggested by K. C. Chen et al. in “DAG-Map: Graph-Based FPGA Technology Mapping for Delay Optimization”, IEEE Design and Test of Computers, September 1992, pp. 7–20, uses a graph based technology mapping package for delay optimization in logic elements. In this technology mapping is carried out in three main parts, transformation of an arbitrary network into a two input network technology mapping for delay minimization, and area optimization in the mapping approach through a direct acyclic graph (DAG).
A polynomial time technology mapping algorithm has been proposed by J. Cong, and Y. Ding in “An 0ptimal Technology Mapping Algorithm for Delay Optimization in Look-up Table Based FPGA Designs”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pages 1–12, January 1994, in which a Flow-Map that optimally maps an electrical circuit on an FPGA for depth minimization by computing a minimum height for k-feasible cut an a network. This process is commonly used for technology mapping. The process can be better understood by referring to the flowchart shown in FIG. 1.
FIG. 1 shows a flow diagram of the process. According to this process, in the first step, the gate level Net-list 1.1 containing information about the logic gates is inserted for mapping onto the LUTs in the FPGA. Now supposing that N denotes the given network of logic gates contained in the Net-list and Nt(v) denotes a sub-network generated at a node v, the next step is to generate sub-network Nt(v) at each node v 1.2 of the network N. The sub-network Nt(v) contains the node v itself along with all the transitive fanins of node v including the primary inputs. Next, k-distinct paths are found in the sub-network Nt(v) by applying known techniques such as depth first, breadth first search and the like. Subsequently, a minimum height k-feasible cut is found in the sub-network Nt(v) 1.3 starting from v until the primary inputs and LUTs are formed. The next step followed in the process is to level each gate of the design 1.4 and subsequently, map the given design starting from the primary output towards the primary inputs 1.5 onto a LUT.
FIG. 2 shows the generation of sub-networks Nt(v) using the process discussed above. In this process at each node v of the network N, in the given figure, sub-network Nt(12) generated at the node 12 starts from node 12 and continues until the primary nodes 1, 2, 3, 4 and 5. Thus, the sub-network can be mathematically represented as Nt(12)={12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1} as it includes all the transitive fanins of node v, including the primary inputs. A four input LUT is formed at node 12 for the sub-network Nt(v). Nodes inside the cone are 10, 11 and 12, while the fanin nodes of the cone are 6, 7, 8 and 9.
Another research article by J. Cong et al. in “On Area/Depth Trade-off in LUT-Based FPGA Technology Mapping”, UCLA Computer Science Dept., 30th ACM/IEEE Design Automation Conference (DAC), 1993, pp. 213–218, suggests a process for FPGA mapping technology. In this technique a number of depth relaxation operations are performed to obtain a new network with bounded increase in depth and is advantageous to subsequent re-mapping for area minimization by gradually increasing depth bound.
An integrated approach for synthesizing and mapping has been disclosed by Francis, et. al. in “Technology Mapping of Lookup Table-Based FPGAs for Performance”, Dept. of Electrical Engineering, University of Toronto, CA, IEEE February 1991, pp. 568–571. This process uses a global combinatorial optimization technique to guide the Boolean synthesis process during depth minimization. The combinatorial optimization is achieved by computing a series of minimum cuts of fixed heights in a network based on fast network computation, and the Boolean optimization is achieved by efficient Ordered Binary Decision Diagrams (OBDD) based implementation of functional decomposition.
In another approach by Francis, et al., a process has been discussed for technology mapping including a new method for choosing gate level decompositions based on binary packing. Several other approaches have also been applied to achieve these objectives. However, most of these approaches result in either local optimal or exponential time complexity. Hence, these approaches are too expensive and cannot be applied for all designs.
One of the ways for achieving this reduction of sub-network includes: Starting from the node v and including all nodes until the k-feasible cut is found; and Considering node v as 0th level node, including all nodes up to a certain level, e.g. 4 or 5. Such reduction techniques do not give an optimal solution or even a near optimal solution.
The Flow-diagram process described above suffers from a drawback, that the runtime of the process gets increased while constructing sub-networks and finding a cut for each node of the circuit. This increase becomes even more prominent when the delay of a circuit increases.